package algorithm.tree.binarytree.misc;

import algorithm.tree.binarytree.base.TreeNode;

import java.util.*;

public class MinPathTree {
    public static int[] parse(int[] args) {
        TreeNode root = parseNode(args, 0);
        Deque<Event> eventDeque = new ArrayDeque<>();
        eventDeque.push(new InitEvent(root));
        List<TreeNode> path = null;
        while (!eventDeque.isEmpty()) {
            Event event = eventDeque.pop();
            switch (event) {
                case InitEvent initEvent -> eventDeque.push(new CollectNodeInfoEvent(initEvent.getRoot()));
                case ReverseSelectNodeEvent reverseSelectNodeEvent -> {
                    List<NodePathInfo> nodePathInfoList = reverseSelectNodeEvent.getNodePathInfoList();
                    NodePathInfo nodePathInfo = nodePathInfoList.get(0);
                    path = nodePathInfo.getPath();
                }
                case SortPathValueEvent sortPathValueEvent -> {
                    List<NodePathInfo> nodePathInfoList = sortPathValueEvent.getNodePathInfoList();
                    nodePathInfoList.forEach(it -> it.pathSum = it.getPath().stream().mapToInt(TreeNode::getValue).sum());
                    nodePathInfoList.sort((NodePathInfo o1, NodePathInfo o2) -> o1.pathSum - o2.pathSum);
                    eventDeque.push(new ReverseSelectNodeEvent(nodePathInfoList));
                }
                case ComputePathValueEvent computePathValueEvent -> {
                    List<NodePathInfo> nodePathInfoList = new ArrayList<>();
                    doVisit(computePathValueEvent.getRoot(), new ArrayList<>(), nodePathInfoList);
                    eventDeque.push(new SortPathValueEvent(nodePathInfoList));
                }
                case CollectNodeInfoEvent collectNodeInfoEvent -> eventDeque.push(new ComputePathValueEvent(collectNodeInfoEvent.getRoot()));
                default -> throw new IllegalStateException("Unexpected value: " + event);
            }
        }
        return path.stream().mapToInt(TreeNode::getIndex).toArray();
    }

    private static void doVisit(TreeNode root, List<TreeNode> path, List<NodePathInfo> nodePathInfoList) {
        if (root == null) {
            if (!path.isEmpty()) {
                NodePathInfo nodePathInfo = new NodePathInfo(path.get(path.size() - 1), new ArrayList<>(path));
                nodePathInfoList.add(nodePathInfo);
            }
        } else {
            List<TreeNode> currentPath = new ArrayList<>(path);
            currentPath.add(root);
            doVisit(root.getLeft(), currentPath, nodePathInfoList);
            doVisit(root.getRight(), currentPath, nodePathInfoList);
        }
    }

    public static abstract class Event {
    }

    public static class InitEvent extends Event {
        TreeNode root;

        public TreeNode getRoot() {
            return root;
        }

        public InitEvent(TreeNode root) {

            this.root = root;
        }
    }

    private static TreeNode parseNode(int[] args, int index) {
        if (args.length > index && args[index] != -1) {
            TreeNode treeNode = new TreeNode(index, args[index]);
            int leftIndex = 2 * index + 1;
            int rightIndex = 2 * index + 2;
            treeNode.setLeft(parseNode(args, leftIndex));
            treeNode.setRight(parseNode(args, rightIndex));
            return treeNode;
        }
        return null;
    }

    private static class ReverseSelectNodeEvent extends Event {
        List<NodePathInfo> nodePathInfoList;

        public ReverseSelectNodeEvent(List<NodePathInfo> nodePathInfoList) {
            super();
            this.nodePathInfoList = nodePathInfoList;
        }

        public List<NodePathInfo> getNodePathInfoList() {
            return nodePathInfoList;
        }
    }

    private static class SortPathValueEvent extends Event {
        List<NodePathInfo> nodePathInfoList;

        public SortPathValueEvent(List<NodePathInfo> nodePathInfoList) {
            super();
            this.nodePathInfoList = nodePathInfoList;
        }

        public List<NodePathInfo> getNodePathInfoList() {
            return nodePathInfoList;
        }
    }

    private static class ComputePathValueEvent extends Event {
        TreeNode root;
        List<TreeNode> leafList;

        public ComputePathValueEvent(TreeNode root) {
            this.root = root;
        }

        public TreeNode getRoot() {
            return root;
        }

        public List<TreeNode> getLeafList() {
            return leafList;
        }
    }

    private static class CollectNodeInfoEvent extends Event {
        TreeNode root;

        public CollectNodeInfoEvent(TreeNode root) {
            this.root = root;
        }

        public TreeNode getRoot() {
            return root;
        }
    }

    private static class NodePathInfo {
        public int pathSum;
        TreeNode leaf;
        List<TreeNode> path;

        public NodePathInfo(TreeNode leaf, List<TreeNode> path) {
            this.leaf = leaf;
            this.path = path;
        }

        public TreeNode getNode() {
            return leaf;
        }

        public List<TreeNode> getPath() {
            return path;
        }
    }


}
